package com.lx.algorithm.temp;

import org.springframework.jdbc.datasource.DataSourceUtils;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-26 15:04:34
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-26     张李鑫                     1.0         1.0 Version
 */
public class StickersToSpellWord {
    /**
     * 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
     * arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
     * 返回需要至少多少张贴纸可以完成这个任务。
     * 例子：str= "babac"，arr = {"ba","c","abcd"}
     * ba + ba + c  3  abcd + abcd 2  abcd+ba 2
     * 所以返回2
     */

    public static void main(String[] args) {

    }


    public static int minStickers(String str, String[] arr) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        return process(str, arr);

    }

    private static int process(String str, String[] arr) {
        if (str.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String i1 : arr) {
            String remove = remove(str, i1);
            if (remove.length() != str.length()) {
                int process = process(remove, arr);
                min = Math.min(min, process);
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }


    public static int minStickers1(String str, String[] arr) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int[][] word = new int[arr.length][26];
        for (int i = 0; i < arr.length; i++) {
            char[] chars = arr[i].toCharArray();
            for (int i1 = 0; i1 < chars.length; i1++) {
                word[i][chars[i1] - 'a'] += 1;
            }
        }

        return process(str, word);
    }

    private static int process(String str, int[][] stickers) {
        char[] chars = str.toCharArray();
        int[] strWord = new int[26];
        for (int i = 0; i < chars.length; i++) {
            strWord[chars[i] - '1'] += 1;
        }

        for (int i = 0; i < stickers.length; i++) {
            int[] sticker = stickers[i];
            if (sticker[chars[0]-'a']>0){
                StringBuffer stringBuffer = new StringBuffer();
                for (int i1 = 0; i1 < 26; i1++) {
                    if (strWord[i1]>0){
                        int nums=strWord[i1]-sticker[i1];
                        for (int i2 = 0; i2 < nums; i2++) {

                        }
                    }
                }
            }
        }
        return 0;
    }


    /**
     * <p>
     * 比较两个字符串是否存在相同字符
     * </p>
     *
     * @param s1
     * @param s2
     * @return java.lang.String
     * @Author zlx
     * @date 2021/10/26
     */
    public static String remove(String s1, String s2) {
        char[] chars = s1.toCharArray();
        char[] chars1 = s2.toCharArray();
        int[] count = new int[26];

        //统计个数  加 减
        for (char aChar : chars) {
            count[aChar - 'a']++;
        }
        for (char aChar : chars1) {
            count[aChar - 'a']--;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                for (int i1 = 0; i1 < count[i]; i1++) {
                    sb.append(i + 'a');
                }
            }
        }
        return sb.toString();
    }


}
